//
//  main.c
//  ChainQueue
//
//  Created by Shawn Li on 2020/4/15.
//  Copyright © 2020 Shawn. All rights reserved.
//

//本工程主要演示链式队列实现

#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"

//对于链式队列理论上来说长度是无限的。不过你也对其最大长度进行限定。
#define MAXSIZE 20

#define SUCCESS 1
#define ERROR 0

#define TRUE 1
#define FALSE 0

typedef int ElementType;
typedef int Status;

//定义队列结点类型，以及指向此类型的指针类型
typedef struct QueueNode{
    ElementType data;
    struct QueueNode *next;
}QueueNode, *QueueNodePtr;

typedef struct ChainQueue{
//    队头 结点从这里出队
    QueueNodePtr front;
//    队尾 结点从这里入队
    QueueNodePtr rear;
//    队列的长度
    int count;
}ChainQueue;


/// 初始化
/// @param q 队列
Status queueInit(ChainQueue *q){
//    注意：这里使用了头结点，当然你也可以不用┗|｀O′|┛ 嗷~~
    q->rear = q->front = (QueueNodePtr)malloc(sizeof(QueueNode));
    q->count = 0;
    return SUCCESS;
}


/// 判断队列是否为空
/// @param q 队列
Status queueIsEmpty(ChainQueue q){
//    当然此处你也可以使用 count 进行判空
    return q.rear == q.front;
}


/// 获取队列的长度
/// @param q 队列
int queueGetCount(ChainQueue q){
    return q.count;
}


/// 清空队列
/// @param q 队列
Status queueClear(ChainQueue *q){
    QueueNodePtr temp;
//    p = q->front;
    while (q->front) {
        temp = q->front;
        q->front = q->front->next;
        free(temp);
    }
//    注意这里：front的位置和长度都需要处理，或者在函数内直接使用front跳步也行(代码改了，采用的这种方法)。
//    q->front = p;
    q->count = 0;
    return SUCCESS;
}


/// 遍历输出队列
/// @param q 队列
Status queuePrint(ChainQueue q){
    if (queueIsEmpty(q)) {
        printf("队列为空，无法输出！\n");
        return ERROR;
    }
    
//    输出的时候不能改变的原结构，所以不能使用队列的指针进行跳步，使用临时指针 p 进行操作。
    QueueNodePtr p;
    p = q.front->next;
    
    printf("队列信息：");
    while (p) {
        printf("%d, ", p->data);
        p = p->next;
    }
    printf("\n\n");
    return SUCCESS;
}


/// 入队
/// @param q 队列
/// @param e 待入队的元素
Status queueIn(ChainQueue *q, ElementType e){
    
//    如果你限定了最大长度，你需要在此处进行容错判断。
    
    QueueNodePtr k;
    
//    准备入队的结点
    k = (QueueNodePtr)malloc(sizeof(QueueNode));
    k->data = e;
    k->next = NULL;
//    入队
    q->rear->next = k;
    q->rear = k;
//    长度处理
    q->count++;
    
    return SUCCESS;
}


/// 出队
/// @param q 队列
/// @param e 出队元素带回
Status queueOut(ChainQueue *q, ElementType *e){
    if (queueIsEmpty(*q)) {
        printf("队列为空，无法出队！");
        return ERROR;
    }
    
    QueueNodePtr temp;
    
//    注意本例是使用了头结点的。所以需要留意此处对于头结点的处理。
    temp = q->front->next;
    q->front->next = q->front->next->next;
//    带回出队结点的值并释放该结点
    *e = temp->data;
    free(temp);
//    长度处理
    q->count--;
    
    return SUCCESS;
}


int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n本工程主要演示链式队列实现！\n\n");
    
    ChainQueue q;
    ElementType e;
    
    queueInit(&q);
    queuePrint(q);
    
    for (int i = 0; i < 21; i++) {
        if (queueIn(&q, i)) {
            queuePrint(q);
        }
    }
    
    printf("\n\n\n***********************************\n\n\n");
    
    for (int i = 0; i < 21; i++) {
        if (queueOut(&q, &e)) {
            printf("\n------出栈元素为：%d\n", e);
            queuePrint(q);
        }
    }
    
    return 0;
}
